package com.breeze.leetcode;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 * 215. 数组中的第K个最大元素
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 */
public class LeetCode215 {
    /**
     * 方法一：内置算法
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     */
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }


    /**
     * 方法二：最大堆
     * 时间复杂度：O(nlogn), TODO：为什么
     * 空间复杂度：O(log n)，即递归使用栈空间的空间代价
     */
    public int findKthLargest2(int[] nums, int k) {
        buildMaxHeap(nums);
        for (int i = 1; i < k; i++) {
            swap(nums, 0, nums.length - i);
            maxHeapify(nums, 0, nums.length - i);
        }
        return nums[0];
    }

    // 构建大根堆
    private void buildMaxHeap(int[] nums) {
        for (int i = nums.length / 2; i >= 0; i--) {
            maxHeapify(nums, i, nums.length);
        }
    }

    // 最大堆化
    private void maxHeapify(int[] nums, int i, int heapSize) {
        int l = i * 2 + 1;
        int r = (i + 1) * 2;
        int largest = i;
        if (l < heapSize && nums[l] > nums[i]) {
            largest = l;
        }
        // 注意：此时r需要和largest比较
        if (r < heapSize && nums[r] > nums[largest]) {
            largest = r;
        }
        if (largest != i) {
            // 更换大值到i的位置
            swap(nums, i, largest);
            // largest的位置需要继续最大堆化
            maxHeapify(nums, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 方法三： TODO: 快速排序、优先队列
     */
    public int findKthLargest3(int[] nums, int k) {
        return nums[0];
    }

    public static void main(String[] args) {
        LeetCode215 leetCode215 = new LeetCode215();
        int[] nums = {3, 2, 1, 5, 6, 4};
        // System.out.println(leetCode215.findKthLargest(nums, 2));
        System.out.println(leetCode215.findKthLargest2(nums, 2));
    }
}
